P1306 斐波那契公约数

数学结论+矩乘简单优化

由于数学结论证明过于巧妙，这里仅放出我看的那篇题解

题解：

转载：见这里

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int mod=1e8;

struct mat{
    int a[2][2];
    mat(){memset(a,0,sizeof a);}
    inline mat operator * (const mat &nt) const {
        mat res;
        for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
            res.a[i][j]=(1ll*res.a[i][j]+1ll*a[i][k]*nt.a[k][j]%mod)%mod;
        return res;
    }
}A,B;

mat mpow(mat x,int y){
    mat res;
    for(int i=0;i<=1;i++)
        res.a[i][i]=1;
    for(;y;y>>=1,x=x*x) if(y&1) res=res*x;
    return res;
}

int n,m;

signed main(){
    read(n);read(m);
    A.a[0][0]=A.a[0][1]=1;
    B.a[0][1]=B.a[1][0]=B.a[1][1]=1;
    write((A*mpow(B,__gcd(n,m)-1)).a[0][0]);
}